Worldwide, the amount of data stored in relational databases is growing. The amount of data is growing in terms of number of rows, simply because of an accumulation of historic data. Data is also growing in terms of increased row size because of additional information requirements. Additionally, data is growing because of the advent of standard software; tailor-made systems are replaced with highly generic standard software that covers many different customers' needs.
As this happens, the average relevance of one byte of stored information is decreasing, since information that is only needed on specific occasions, specific customers, or specific users is being added to databases.
On the other hand, due to the world-wide use of information available on the Internet, centralized services have become more and more important. More and more time-critical online applications are arriving. Users of these applications we want queries to return a result within one or two seconds. These two trends—more information, but less process time—contradict each other. Consequently, returning a result set in due time becomes increasingly difficult for the database system.
In database systems, a module called the query optimizer is assigned the task of calculating a fast access plan. The access plan depends to a significant extent on the selection criteria provided by the user. When a good selection criterion is given, the query optimizer uses that criterion by scanning an index. When only a bad selection criterion is given, the query optimizer produces a result set based on full table scans.
The most difficult situation arises when two or more medium selection criteria on different tables exist. A medium selection criterion, as used herein, is one that produces a small relative result set, but still a large absolute result set. A selection criterion that results in 5% of the rows or less is a small relative result set. To resolve such a criterion, the query optimizer should use an index scan (5% is an approximate number; the actual calculation of whether or not to use an index may be far more complex). Depending on the size of the table, 5% of the rows could still be tens of thousands rows or more, which is a large absolute result set. Very large result sets are less likely to be returned quickly in response to a query. Thus, a growing number of rows in database tables may result in an increasingly slower response time.
The following query may be considered for purposes of illustration. A user might want to obtain a result set that includes all people living in New York City who are also over the age of 65. The user might want to obtain this result set from a database that represents the complete U.S. population. The data might be stored in two tables. An “address” table contains, along with other columns, the columns “city” and “person_id.” The column “person_id” refers to another table, “person.” Table “person” contains, along with other columns, the column “age” and the column “person_id” as primary key. Under these circumstances, the query will involve two selection criteria: “city=New York City” and “age>65.” The criterion “city=New York City” will yield roughly 3% of the U.S population, but above eight million rows in absolute numbers. The “over the age of 65” criterion represents roughly 13% of the U.S. population—that is, more than forty million rows.
Since the criterion “city=New York City” is applied on the table “address” and “age>65” goes against the table “person,” the query optimizer cannot, under normal circumstances, combine these two filter criteria. Thus, the query optimizer has to choose, for a start point, either “address” or “person.” Assuming that the query optimizer starts with the access to “address,” the database will read all addresses in New York City. The database will then join in the “person” data. Next, the database uses the other filter, “age>65,” which causes only 13% of the rows from the previous step to be kept; the rest are thrown away. In other words, 87% of the data read from table “address” is thrown away. This is not very efficient.
Even when the users wants to retrieve the first 100 rows of the result set, about 1300 rows still need to be read from table “address.”
In actuality, the situation may be worse than is implied above. Most database systems have no means for just reading a row by itself. Instead, these database systems will always read, from disk or memory, an entire data block that contains multiple rows. Such a data block may contain less than 10 rows or more than 100 rows, depending on the size of a row. When rows are very large, few of them will fit in one database block. When data blocks contain few rows, the likelihood is increased that many blocks will need to be read to find the rows that are wanted. Increasing row size is one of the factors that damages performance.
A technique for dealing with these kinds of queries, which still provides good performance, is needed.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.